package fireway;

import java.util.Stack;

/**
 * 三角数学的递归转化为基于栈的方法示例
 * 2018年 07月 08日 星期日
 *
 * @author fireway
 */
public class TriangleNumber {
    private static final boolean DEBUG = false;

    private static final int ADDR_INIT_CALL = 0x01;    // 初次调用，把用户输入的值以及返回值6压入栈中

    private static final int ADDR_METHOD_ENTRY = 0x02;  // 方法的入口

    private static final int ADDR_METHOD_CALL = 0x03;   // 递归地调用自身

    private static final int ADDR_CALCULATION = 0x04;   // 计算

    private static final int ADDR_METHOD_EXIT = 0x05;   // 方法的出口

    private static final int ADDR_RETURN_POINT = 0x06;   // 当程序返回时控制将要转到的地方

    public int calcN(int n) {
        int result = recCalc(n);
        return result;
    }

    private int recCalc(int n) {
        int nRet = 0;

        Stack<Param> stack = new Stack<Param>();
        int funcAddress = ADDR_INIT_CALL;

        while (true) {
            if (DEBUG) {
                System.out.println("0x" + Integer.toHexString(funcAddress) + ": result[" + nRet + "], Stack = " + stack);
            }

            switch(funcAddress) {
                case ADDR_INIT_CALL: {
                    Param param = new Param();
                    param.setN(n);
                    param.setReturnAddress(ADDR_RETURN_POINT);
                    stack.push(param);
                    funcAddress = ADDR_METHOD_ENTRY;
                    break;
                }

                case ADDR_METHOD_ENTRY: {
                    Param param = stack.peek();
                    if (1 == param.getN()) {
                        nRet = 1;
                        funcAddress = ADDR_METHOD_EXIT;
                    } else {
                        funcAddress = ADDR_METHOD_CALL;
                    }
                    break;
                }

                case ADDR_METHOD_CALL: {
                    Param param = new Param();
                    param.setN(stack.peek().getN() - 1);
                    param.setReturnAddress(ADDR_CALCULATION);
                    stack.push(param);
                    funcAddress = ADDR_METHOD_ENTRY;
                    break;
                }

                case ADDR_CALCULATION: {
                    nRet += stack.peek().getN();
                    funcAddress = ADDR_METHOD_EXIT;
                    break;
                }

                case ADDR_METHOD_EXIT: {
                    Param param = stack.peek();
                    funcAddress = param.getReturnAddress();
                    stack.pop();
                    break;
                }

                case ADDR_RETURN_POINT: {
                    return nRet;
                }

                default: {
                    System.out.println("there is not function address " + funcAddress);
                    break;
                }
            }
        }
    }

    /**
     * Param类封装了返回地址和这个方法的形参n
     */
    private class Param {
        private int mN;    // 参数n

        private int mReturnAddress;    // 返回地址

        public int getN() {
            return mN;
        }

        public void setN(int n) {
            mN = n;
        }

        public int getReturnAddress() {
            return mReturnAddress;
        }

        public void setReturnAddress(int returnAddress) {
            mReturnAddress = returnAddress;
        }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer();
            sb.append("formatParam[");
            sb.append(mN);
            sb.append("], returnAddress[0x");
            sb.append(Integer.toHexString(mReturnAddress));
            sb.append("]");
            return sb.toString();
        }
    }
}
